#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# ======================================================
# @File:      : test51
# @Author     : forward_huan
# @Date       : 2024/11/20 21:29
# @Desc       :
# ======================================================
from typing import List


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        visited = [["."] * n for _ in range(n)]
        row_used, col_used = [0] * n, [0] * n
        result = []
        for col in range(n):
            self.dsf(0, col, row_used, col_used, n, visited, result)
        return result

    @staticmethod
    def is_valid(row, col, n, row_used, col_used, visited):
        reduce, add = row - col, row + col
        if row_used[row] == 1 or col_used[col] == 1:
            return False
        for r in range(row):
            for c in range(n):
                if c == col:
                    continue
                if col_used[col] == 1:
                    return False
                if row == r or col == c or (r - c) == reduce or (r + c) == add:
                    if visited[r][c] != ".":
                        return False
        return True

    @staticmethod
    def generate_result(result):
        return ["".join(item) for item in result]

    def dsf(self, row, col, row_used, col_used, n, visited, result):
        if row >= n:
            temp = self.generate_result(visited)
            if temp not in result:
                result.append(self.generate_result(visited))
            return
        if not self.is_valid(row, col, n, row_used, col_used, visited):
            return

        for c in range(n):
            row_used[row], col_used[col], visited[row][col] = 1, 1, "Q"
            self.dsf(row + 1, c, row_used, col_used, n, visited, result)
            row_used[row], col_used[col], visited[row][col] = 0, 0, "."


print(Solution().solveNQueens(n=4))
